package midalgorithms.backtrack;

import java.util.*;

public class _02GenerateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        Deque<Character> validParenthesis = new LinkedList<>();
        backtrack(res,validParenthesis,n,0,0);
        return res;
    }

    private static void backtrack(List<String> res, Deque<Character> validParenthesis, int n, int leftNum,int rightNum) {
        //  递归终止条件
        if (validParenthesis.size() == 2*n){
            //  栈满
            //  存放结果集
            StringBuilder stringBuilder = new StringBuilder();
            for (Character character : validParenthesis){
                stringBuilder.append(character);
            }
            res.add(stringBuilder.toString());
            return;
        }
        //  回溯
        //  如果可以继续添加括号，则执行入队操作
        //  本题的难点就是如何在回溯的执行中，正确添加括号！！！
        //  核心思想是右括号一定是添加左括号之后再添加的
        if (leftNum < n){
            //  可以添加左括号：
            validParenthesis.addLast('(');
            backtrack(res,validParenthesis,n,leftNum+1,rightNum);
            validParenthesis.poll();
        }
        if (leftNum > rightNum){
            //  可以添加右括号
            validParenthesis.addLast(')');
            backtrack(res,validParenthesis,n,leftNum,rightNum+1);
            validParenthesis.poll();
        }
    }
}
